1. Field of the Invention
The invention relates to telecommunications networks. More particularly, the invention relates to a method of multicasting data through a telecommunications network switch.
2. State of the Art
One of the earliest techniques for employing broadband telecommunications networks was called time division multiplexing (TDM). The basic operation of TDM is simple to understand. A high frequency signal is divided into multiple time slots within which multiple lower frequency signals can be carried from one point to another. The actual implementation of TDM is quite complex, however, requiring sophisticated framing techniques and buffers in order to accurately multiplex and demultiplex signals. The North American standard for TDM (known as T1 or DS1) utilizes twenty-four interleaved channels together having a rate of 1.544 Mbits/sec. The European standard for TDM is known as E-1 and utilizes thirty interleaved channels having a rate of 2.048 Mbits/sec. A hierarchy of multiplexing is based on multiples of the T1 or E-1 signal, one of the most common being T3 or DS3. A T3 signal has 672 channels, the equivalent of twenty-eight T1 signals. TDM was originally designed for voice channels. Today, however, it is used for both voice and data.
An early approach to broadband data communication was called packet switching. One of the differences between packet switching and TDM is that packet switching includes methods for error correction and retransmission of packets which become lost or damaged in transit. Another difference is that, unlike the channels in TDM, packets are not necessarily fixed in length. Further, packets are directed to their destination based on addressing information contained within the packet. In contrast, TDM channels are directed to their destination based on their location in the fixed frame. Today, a widely used packet switching protocol is known as IP (Internet Protocol).
More recently, broadband technologies known as ATM and SONET have been developed. The ATM network is based on fixed length packets (cells) of 53-bytes each (48-bytes payload with 5-bytes overhead). One of the characteristics of the ATM network is that users contract for a quality of service (QOS) level. Thus, ATM cells are assigned different priorities based on QOS. For example, constant bit rate (CBR) service is the highest priority service and is substantially equivalent to a provisioned TDM connection. Variable bit rate (VBR) service is an intermediate priority service which permits the loss of cells during periods of congestion. Unspecified bit rate (UBR) service is the lowest priority and is used for data transmission which can tolerate high latency such as e-mail transmissions.
The SONET network is based on a frame of 810-bytes within which a 783-byte synchronous payload envelope (SPE) floats. The payload envelope floats because of timing differences throughout the network. The exact location of the payload is determined through a relatively complex system of stuffs/destuffs and pointers. In North America, the basic SONET signal is referred to as STS-1 (or OC-1). The SONET network includes a hierarchy of SONET signals wherein up to 768 STS-1 signals are multiplexed together providing the capacity of 21,504 T1 signals (768 T3 signals). STS-1 signals have a frame rate of 51.84 Mbit/sec, with 8,000 frames per second, and 125 microseconds per frame. In Europe, the base (STM-1) rate is 155.520 Mbit/sec, equivalent to the North American STS-3 rate (3*51.84=155.520), and the payload portion is referred to as the virtual container (VC). To facilitate the transport of lower-rate digital signals, the SONET standard uses sub-STS payload mappings, referred to as Virtual Tributary (VT) structures. (The ITU calls these Tributary Units or TUs.) Four virtual tributary sizes are defined: VT-1.5, VT-2, VT-3 and VT-6. VT-1.5 has a data transmission rate of 1.728 Mbit/s and accommodates a T1 signal with overhead. VT-2 has a data transmission rate of 2.304 Mbit/s and accommodates an E1 signal with overhead. VT-3 has a data transmission rate of 3.456 Mbit/s and accommodates a T2 signal with overhead. VT-6 has a data transmission rate of 6.912 Mbit/s and accommodates a DS2 signal with overhead.
Each of the above described broadband technologies can be categorized as TDM, ATM, or Packet technologies, with SONET being a complex form of TDM. From the foregoing, it will be appreciated that TDM, ATM and Packet each have their own unique transmission requirements. Consequently, different kinds of switches are used to route these different kinds of signals. In particular, TDM requires careful time synchronization; ATM requires careful attention to the priority of cells and QOS; and packet (e.g. IP) requires the ability to deal with variable length packets. For these reasons, switching technologies for TDM, ATM, and variable length packet switching have evolved in different ways. Service providers and network designers have thus been forced to deal with these technologies separately, often providing overlapping networks with different sets of equipment which can only be used within a single network.
It is therefore an object of the invention to provide methods and apparatus whereby different kinds of broadband signals can be switched through a single switching fabric.
It is also an object of the invention to provide a network element which can switch TDM, ATM, and variable length packet traffic all through the same switch fabric.
It is another object of the invention to provide a network switch chipset which can be combined with identical chip sets to provide a scalable network switch fabric.
It is a further object of the invention to provide a network switch which allows flexible partitioning among TDM, ATM, and variable length packet traffic.
Another object of the invention is to provide a network switch with redundant switch planes so that the failure of switch elements or links does not immediately cause a connection failure.
A further object of the invention is to provide a network switch which handles multicast as well as unicast voice and data transmission.
An additional object of the invention to provide a network switch which supports Clos architectures as well as folded Clos architectures.
In accord with these objects which will be discussed in detail below, the network switch of the present invention includes at least one port processor (also referred to in the appendices as a xe2x80x9cservice processorxe2x80x9d) and at least one switch element. The port processor has a SONET OC-x (SONET/SDH STS-x/STM-y) interface (for TDM traffic), a UTOPIA and UTOPIA-frame based interface (for ATM and packet traffic), and an interface to the switch element. An exemplary port processor has a total I/O bandwidth equivalent to a SONET OC-48 signal. An exemplary switch element has 12xc3x9712 ports and supports a total bandwidth of 30 Gbps.
A typical switch according to the invention includes multiple port processors and multiple switch elements. For a 48xc3x9748 xe2x80x9cfoldedxe2x80x9d switch, 48 port processors are coupled (four each) to 12 (first and third stage) switch elements and each of these twelve switch elements is coupled to 8 (second stage) switch elements. A three stage non-blocking switch according to the invention provides a total bandwidth of 240 Gbps and a five stage non-blocking switch provides a total bandwidth of 1 Tbps. An exemplary three stage folded Clos architecture switch includes forty-eight port processors and twenty switch elements. Four port processors are coupled to each of twelve (first and third stage) switch elements. Each of the twelve (first and third stage) switch elements are coupled to eight (second stage) switch elements. According to the presently preferred embodiment, each port processor is provided with means for coupling to two ports of a switch element or one port of two switch elements thereby providing redundancy in the event of a link failure.
According to the invention, a data frame of 9 rows by 1700 slots is used to transport ATM, TDM, and Packet data from a port processor through one or more switch elements to the same or another port processor. Each frame is transmitted in 125 microseconds, each row in 13.89 microseconds. Each slot includes a four-bit tag plus a four-byte payload (i.e., thirty-six bits). The slot bandwidth ({fraction (1/1700)} of the total frame) is 2.592 Mbps which is large enough to carry an E-1 signal with overhead. The four-bit tag is a cross connect pointer which is set up when a TDM connection is provisioned. The last twenty slots of the frame are reserved for link overhead. Thus, the frame is capable of carrying the equivalent of 1,680 E-1 TDM signals even though an STM-16 frame has a capacity of only 1008 E-1 signals.
For ATM and packet data, a PDU (protocol data unit) of sixteen slots is defined for a sixty-four-byte payload (large enough to accommodate an ATM cell with switch overhead). A maximum of ninety-six PDUs per row is permitted. The sixteen four-bit tags of a PDU are not needed for PDU routing so they are used as parity bits to protect the ATM or variable length packet payload. Of the sixty-four-byte payload, twelve bytes (96 bits) are used by the switch for internal routing. This leaves fifty-two bytes for actual payload which is sufficient to carry an ATM cell (without the one-byte HEC) and sufficient for larger packets after fragmentation. The PDUs are self-routed through the switch with a twenty-eight-bit routing tag which allows routing through seven switch stages using four-bits per stage. The remaining sixty-eight bits of the PDU are used for various other addressing information such as indicating whether the PDU contains an ATM cell, a packet, or a control message, whether reassembly of the packet should be aborted, whether the payload is a first fragment, middle fragment or last fragment, how many payload bytes are in the last fragment, the fragment sequence count, and a destination flow identifier.
The link overhead (LOH) in the last twenty slots of the frame is analogous in function to the line and section overhead in a SONET frame. The LOH may contain a 36-bit frame alignment pattern which is used to delineate the byte and row boundaries from serial data streams, a 32-bit status register for each output link, a 32-bit switch and link identifier, and a 32-bit stuff pattern.
Since ATM and Packet traffic are typically not provisioned, bandwidth must be arbitrated among ATM and Packet connections as traffic enters the system. Moreover, since TDM traffic shares the same frame as ATM and Packet traffic, bandwidth must be arbitrated while maintaining TDM timing. According to the invention, bandwidth is arbitrated by a system of requests and grants which is implemented for each PDU in each row of the frame. The switch elements provide three channels per link, two of which are used to carry data and arbitration requests and one of which is used to carry arbitration grants. According to the presently preferred embodiment, a forty-eight-bit (1.5 slot) request element is generated for each PDU in the next row of the frame. Each switch element includes a single request parser and a separate request arbitration module for each output link. The request elements are generated by the port processors and include intra-switch xe2x80x9chop-by-hopxe2x80x9d routing tags and priority level information. Request elements are buffered by the switch elements and low priority request elements are discarded by a switch element if the buffer fills. Each request element which is not discarded as it travels through the switch fabric is returned to the port processor from which it originated during one xe2x80x9crow timexe2x80x9d, i.e. 13.89 microseconds. As suggested above, requests are made xe2x80x9cin bandxe2x80x9d interleaved with data and grants (the returned request elements) are made xe2x80x9cout of bandxe2x80x9d using the third channel in each link.
In order to maintain timing for TDM traffic, the V1-V4 bytes in the VT/VC frame are stripped off and the VC bytes are buffered at ingress to the switch by a port processor. The V1-V4 bytes are regenerated at the egress from the switch by a port processor. In rows having both PDU and TDM traffic, the PDUs are configured early and the TDM slots are configured late in the row.
According to the presently preferred embodiments, each switch element includes a multicast controller and a separate multicast PDU buffer. Two alternate embodiments are provided for multicasting. The first embodiment requires fewer gates and is best suited for an environment where multicasting is not a major portion of the traffic. The second embodiment requires many more gates to implement. However, it is better suited in an environment where multicasting is a frequent event. The second embodiment requires more latency in setting up a multicast path, but less latency in multicasting data. According to the first embodiment, multicast request elements flow through the switch in the same manner as standard unicast request elements. At the point where the message needs to be multicast, the hop-by-hop field""s bit code for that switch stage indicates that the request is multicast. The request is forwarded to the multicast controller. On the grant path, the multicast controller sources a grant if there is room for the data in the multicast recirculating buffers. Once the data has been transmitted to the multicast buffer, the multicast controller examines the data header and determines on which output links it needs to be sent out. At this point, the multicast controller sources a number of request messages which are handled in the same manner as unicast requests. The process repeats with the sequence of send request, receive grant, transmit PDU. I.e, before each multicast PDU is transmitted, a request and a grant must traverse the switch. According to the second embodiment, a multicast path is reserved for a period of time by sending multiple requests (one for each hop) until all hops have been granted. Once the path is set up in this manner, PDUs are multicast one after the other with no latency until the reserved time expires or there are no more PDUs to transmit.